package com.roy.wakeupes.utils;

import java.util.*;

public class BackwardMaximumMatching {

    public static void main(String[] args) {
        String text = "自然语言处理是人工智能和语言学领域的分支学科自然语言处理是人工智能和语言学领域的分支学科自然语言处理是人工智能和语言学领域的分支学科自然语言处理是人工智能和语言学领域的分支学科自然语言处理是人工智能和语言学领域的分支学科自然语言处理是人工智能和语言学领域的分支学科自然语言处理是人工智能和语言学领域的分支学科自然语言处理是人工智能和语言学领域的分支学科自然语言处理是人工智能和语言学领域的分支学科";
        List<String> dictionary = new ArrayList<>();
        // 假设词典已经加载
        dictionary.add("自然");
        dictionary.add("语言");
//        dictionary.add("处理");
//        dictionary.add("是");
        dictionary.add("人工智能");
//        dictionary.add("和");
        dictionary.add("语言学");
        dictionary.add("领域的");
        dictionary.add("分支");
        dictionary.add("学科");
        dictionary.add("支学科");

        List<String> tokens = tokenize(text, dictionary);
        System.out.println(tokens);
    }

    public static List<String> tokenize(String text, List<String> dictionary) {
        Set<String> tokens = new HashSet<>();
        int end = text.length();
        List<String> words =new ArrayList<>();

        while (end > 0) {
            String matchedWord = null;
            // 从当前位置向前查找最大的匹配词
            for (int i = end; i >= 0; i--) {
                String word = text.substring(i, end);
                if (dictionary.contains(word)) {
//                    matchedWord = word;
                    words.add(word);
//                    break;
                }
            }

//            if (matchedWord != null) {
            if (words.size()>0) {
                // 如果找到匹配词，添加到结果列表
//                tokens.add(matchedWord);
                tokens.addAll(words);
//                // 更新end为匹配词的起始位置
//                end -= matchedWord.length();
                end--;
            } else {
                // 如果没有找到匹配词，每次减少一个字符继续查找
                end--;
            }
        }

        // 因为是从右向左匹配，所以需要反转结果列表
        return new ArrayList<>(tokens);
    }
}